package algorithm.leetcode;

public class NO33_搜索旋转排序数组 {
    static class Solution {

        public int search(int[] nums, int target) {
            int k = findK(nums);
            int ans = findIndexBinary(nums, target, 0, k);
            if (ans == -1) {
                ans = findIndexBinary(nums, target, k + 1, nums.length - 1);
            }
            return ans;
        }

        private int findK(int[] nums) {
            int k = 0;
            while (k + 1 < nums.length && nums[k] < nums[k + 1]) {
                k++;
            }
            return k;
        }

        private int findIndexBinary(int[] nums, int target, int left, int right) {
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (nums[mid] < target) {
                    left = mid + 1;
                } else if (nums[mid] > target) {
                    right = mid - 1;
                } else {
                    return mid;
                }
            }
            return -1;
        }
    }
}


/*
昊哥锐评：
12000 * 0.92 = 11040 + 2500 = 13540
11600 * 0.95 = 11020 + 2400 = 13420
 */